package dataStructure;

public class LinkedList {
    private Node head = null;
    private int length = 0;

    LinkedList(){

    }

    LinkedList(Node node){
        this.head = node;
        length = 1;
    }

    /**
     * 添加元素
     * @param item
     */
    public void add(Integer item){
        Node newNode = new Node(item);
        if(head == null){
            //链表为空，则设置表头指针
            head = newNode;
        } else {
            //链表不可为空，则在表尾插入
            Node cur = head;
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = newNode;
        }
        length ++;
    }

    /**
     * 删除元素
     * @param position
     */
    public void delete(Integer position){
        if(position >=length || position <0) {
            System.out.println("位置在链表外,拒绝删除");
            return;
        } else if(position  == 0){
            head = head.next;
        } else{
            Node pre = null;
            Node next = head;
            while(position -- != 0){
                pre = next;
                next = next.next;
            }
            pre.next = next.next;
        }
        length --;
    }

    /**
     * 获取元素
     * @param position
     * @return
     */
    public Integer get(Integer position){
        if(position >=length || position <0) {
            System.out.println("位置在链表外,获取失败");
            return null;
        } else{
            Node cur = head;
            while(position -- != 0){
                cur = cur.next;
            }
            return cur.item;
        }
    }

    /**
     * 输出链表
     */
    public void print(){
        Node cur = head;
        for(int i =0;i < length;i ++){
            System.out.println(cur.item);
            cur = cur.next;
        }
    }

    /**
     * 逆序输出链表
     */
    public void printReversingly(){
        Node cur = head;
        printReversinglyImpl(cur);
    }

    /**
     * 逆序输出链表实现(递归)
     */
    private void printReversinglyImpl(Node cur){
        if(cur != null){
            if(cur.next != null){
                printReversinglyImpl(cur.next);
            }
            System.out.println(cur.item);
        }
    }

    /**
     * 反转链表
     */
    public void reverse(){
        Node cur = head;
        reverseRsv(cur);
    }

    /**
     * 反转链表实现(递归)
     */
    private void reverseRsv(Node cur){
        if(cur != null){
            if(cur.next != null){
                reverseRsv(cur.next);
            } else{
                head = cur;
                return ;
            }
            cur.next.next = cur;
            cur.next = null;
        }
    }
}
